面试官：你知道哪些限流方案？

前语：不要为了读文章而读文章，一定要带着问题来读文章，勤思考。在此，建议大家为本公众号加“星标”。如文章写得好，望大家阅读后在右下边“在看”处点个赞，以示鼓励！

本文转自公众号：张狗蛋的技术之路。

Java单机限流可以使用AtomicInteger，RateLimiter或Semaphore来实现，但是上述方案都不支持集群限流。集群限流的应用场景有两个，一个是网关，常用的方案有Nginx限流和Spring Cloud Gateway，另一个场景是与外部或者下游服务接口的交互，因为接口限制必须进行限流。

本文的主要内容为：

• Redis和Lua的使用场景和注意事项，比如说KEY映射的问题。

• Spring Cloud Gateway中限流的实现。

# 集群限流的难点

我们来探讨一下，如果将 RateLimiter扩展，让它支持集群限流，会遇到哪些问题。

RateLimiter会维护两个关键的参数 nextFreeTicketMicros和 storedPermits，它们分别是下一次填充时间和当前存储的令牌数。当 RateLimiter的 acquire函数被调用时，也就是有线程希望获取令牌时， RateLimiter会对比当前时间和 nextFreeTicketMicros，根据二者差距，刷新 storedPermits，然后再判断更新后的 storedPermits是否足够，足够则直接返回，否则需要等待直到令牌足够「Guava RateLimiter的实现比较特殊，并不是当前获取令牌的线程等待，而是下一个获取令牌的线程等待」。

由于要支持集群限流，所以 nextFreeTicketMicros和 storedPermits这两个参数不能只存在JVM的内存中，必须有一个集中式存储的地方。而且，由于算法要先获取两个参数的值，计算后在更新两个数值，这里涉及到竞态限制，必须要处理并发问题。

集群限流由于会面对相比单机更大的流量冲击，所以一般不会进行线程等待，而是直接进行丢弃，因为如果让拿不到令牌的线程进行睡眠，会导致大量的线程堆积，线程持有的资源也不会释放，反而容易拖垮服务器。

# Redis和Lua

分布式限流本质上是一个集群并发问题，Redis单进程单线程的特性，天然可以解决分布式集群的并发问题。所以很多分布式限流都基于Redis，比如说Spring Cloud的网关组件Gateway。

Redis执行Lua脚本会以原子性方式进行，单线程的方式执行脚本，在执行脚本时不会再执行其他脚本或命令。并且，Redis只要开始执行Lua脚本，就会一直执行完该脚本再进行其他操作，所以Lua脚本中不能进行耗时操作。使用Lua脚本，还可以减少与Redis的交互，减少网络请求的次数。

Redis中使用Lua脚本的场景有很多，比如说分布式锁，限流，秒杀等，总结起来，下面两种情况下可以使用Lua脚本:

• 使用 Lua 脚本实现原子性操作的CAS，避免不同客户端先读Redis数据，经过计算后再写数据造成的并发问题。

• 前后多次请求的结果有依赖时，使用 Lua 脚本将多个请求整合为一个请求。
  

但是使用Lua脚本也有一些注意事项：

• 要保证安全性，在 Lua 脚本中不要定义自己的全局变量，以免污染 Redis内嵌的Lua环境。因为Lua脚本中你会使用一些预制的全局变量，比如说 redis.call()

• 要注意 Lua 脚本的时间复杂度，Redis 的单线程同样会阻塞在 Lua 脚本的执行中。

• 使用 Lua 脚本实现原子操作时，要注意如果 Lua 脚本报错，之前的命令无法回滚，这和Redis所谓的事务机制是相同的。

• 一次发出多个 Redis 请求，但请求前后无依赖时，使用 pipeline，比 Lua 脚本方便。

• Redis要求单个Lua脚本操作的key必须在同一个Redis节点上。解决方案可以看下文对Gateway原理的解析。

# 性能测试

Redis虽然以单进程单线程模型进行操作，但是它的性能却十分优秀。总结来说，主要是因为:

• 绝大部分请求是纯粹的内存操作

• 采用单线程,避免了不必要的上下文切换和竞争条件

• 内部实现采用非阻塞IO和epoll，基于epoll自己实现的简单的事件框架。epoll中的读、写、关闭、连接都转化成了事件，然后利用epoll的多路复用特性，绝不在io上浪费一点时间。

所以，在集群限流时使用Redis和Lua的组合并不会引入过多的性能损耗。我们下面就简单的测试一下，顺便熟悉一下涉及的Redis命令。

1. # test.lua脚本的内容

2. local test = redis.call("get", "test")

3. local time = redis.call("get", "time")

4. redis.call("setex", "test", 10, "xx")

5. redis.call("setex", "time", 10, "xx")

6. return {test, time}

7. # 将脚本导入redis，之后调用不需再传递脚本内容

8. redis-cli -a 082203 script load "$(cat test.lua)"

9. "b978c97518ae7c1e30f246d920f8e3c321c76907"

10. # 使用redis-benchmark和evalsha来执行lua脚本

11. redis-benchmark -a 082203 -n 1000000 evalsha b978c97518ae7c1e30f246d920f8e3c321c76907 0

12. ======

13. 1000000 requests completed in 20.00 seconds

14. 50 parallel clients

15. 3 bytes payload

16. keep alive: 1

17. 93.54% <= 1 milliseconds

18. 99.90% <= 2 milliseconds

19. 99.97% <= 3 milliseconds

20. 99.98% <= 4 milliseconds

21. 99.99% <= 5 milliseconds

22. 100.00% <= 6 milliseconds

23. 100.00% <= 7 milliseconds

24. 100.00% <= 7 milliseconds

25. 49997.50 requests per second

通过上述简单的测试，我们可以发现本机情况下，使用Redis执行Lua脚本的性能极其优秀，一百万次执行，99.99%在5毫秒以下。

本来想找一下官方的性能数据，但是针对Redis + Lua的性能数据较少，只找到了几篇个人博客，感兴趣的同学可以去探索。

以上lua脚本的性能大概是zadd的70%-80%，但是在可接受的范围内，在生产环境可以使用。负载大概是zadd的1.5-2倍，网络流量相差不大，IO是zadd的3倍，可能是开启了AOF，执行了三次操作。

# Spring Cloud Gateway的限流实现

Gateway是微服务架构 SpringCloud的网关组件，它基于Redis和Lua实现了令牌桶算法的限流功能，下面我们就来看一下它的原理和细节吧。

Gateway基于Filter模式，提供了限流过滤器 RequestRateLimiterGatewayFilterFactory。只需在其配置文件中进行配置，就可以使用。具体的配置感兴趣的同学自行学习，我们直接来看它的实现。

RequestRateLimiterGatewayFilterFactory依赖 RedisRateLimiter的 isAllowed函数来判断一个请求是否要被限流抛弃。

1. public Mono<Response> isAllowed(String routeId, String id) {

2. //routeId是ip地址，id是使用KeyResolver获取的限流维度id，比如说基于uri,IP或者用户等等。

3. Config routeConfig = loadConfiguration(routeId);

4. // 每秒能够通过的请求数

5. int replenishRate = routeConfig.getReplenishRate();

6. // 最大流量

7. int burstCapacity = routeConfig.getBurstCapacity();

8. try {

9. // 组装Lua脚本的KEY

10. List<String> keys = getKeys(id);

11. // 组装Lua脚本需要的参数，1是指一次获取一个令牌

12. List<String> scriptArgs = Arrays.asList(replenishRate + "",

13. burstCapacity + "", Instant.now().getEpochSecond() + "", "1");

14. // 调用Redis，tokens_left = redis.eval(SCRIPT, keys, args)

15. Flux<List<Long>> flux = this.redisTemplate.execute(this.script, keys,

16. scriptArgs);

17. ..... // 省略

18. }

19. static List<String> getKeys(String id) {

20. String prefix = "request_rate_limiter.{" + id;

21. String tokenKey = prefix + "}.tokens";

22. String timestampKey = prefix + "}.timestamp";

23. return Arrays.asList(tokenKey, timestampKey);

24. }

需要注意的是 getKeys函数的prefix包含了"{id}"，这是为了解决Redis集群键值映射问题。Redis的KeySlot算法中，如果key包含{}，就会使用第一个{}内部的字符串作为hash key，这样就可以保证拥有同样{}内部字符串的key就会拥有相同slot。Redis要求单个Lua脚本操作的key必须在同一个节点上，但是Cluster会将数据自动分布到不同的节点，使用这种方法就解决了上述的问题。

然后我们来看一下Lua脚本的实现，该脚本就在Gateway项目的resource文件夹下。它就是如同 Guava的 RateLimiter一样，实现了令牌桶算法，只不过不在需要进行线程休眠，而是直接返回是否能够获取。

1. local tokens_key = KEYS[1]

2. -- request_rate_limiter.${id}.tokens 令牌桶剩余令牌数的KEY值

3. local timestamp_key = KEYS[2]

4. -- 令牌桶最后填充令牌时间的KEY值

5. local rate = tonumber(ARGV[1])

6. -- replenishRate 令令牌桶填充平均速率

7. local capacity = tonumber(ARGV[2])

8. -- burstCapacity 令牌桶上限

9. local now = tonumber(ARGV[3])

10. -- 得到从 1970-01-01 00:00:00 开始的秒数

11. local requested = tonumber(ARGV[4])

12. -- 消耗令牌数量，默认 1

13. local fill_time = capacity/rate

14. -- 计算令牌桶填充满令牌需要多久时间

15. local ttl = math.floor(fill_time*2)

16. -- *2 保证时间充足

17. local last_tokens = tonumber(redis.call("get", tokens_key))

18. -- 获得令牌桶剩余令牌数

19. if last_tokens == nil then

20. -- 第一次时，没有数值，所以桶时满的

21. last_tokens = capacity

22. end

23. local last_refreshed = tonumber(redis.call("get", timestamp_key))

24. -- 令牌桶最后填充令牌时间

25. if last_refreshed == nil then

26. last_refreshed = 0

27. end

28. local delta = math.max(0, now-last_refreshed)

29. -- 获取距离上一次刷新的时间间隔

30. local filled_tokens = math.min(capacity, last_tokens+(delta*rate))

31. -- 填充令牌，计算新的令牌桶剩余令牌数 填充不超过令牌桶令牌上限。

32. local allowed = filled_tokens >= requested

33. local new_tokens = filled_tokens

34. local allowed_num = 0

35. if allowed then

36. -- 若成功，令牌桶剩余令牌数(new_tokens) 减消耗令牌数( requested )，

37. -- 并设置获取成功( allowed_num = 1 ) 。

38. new_tokens = filled_tokens - requested

39. allowed_num = 1

40. end

41. -- 设置令牌桶剩余令牌数( new_tokens ) ，令牌桶最后填充令牌时间(now)

42. -- ttl是超时时间

43. redis.call("setex", tokens_key, ttl, new_tokens)

44. redis.call("setex", timestamp_key, ttl, now)

45. -- 返回数组结果

46. return { allowed_num, new_tokens }

# 后记

Redis的主从异步复制机制可能丢失数据，出现限流流量计算不准确的情况，当然限流毕竟不同于分布式锁这种场景，对于结果的精确性要求不是很高，即使多流入一些流量，也不会影响太大。

正如Martin在他质疑Redis分布式锁RedLock文章中说的，Redis的数据丢弃了也无所谓时再使用Redis存储数据。

I think it’s a good fit in situations where you want to share some transient, approximate, fast-changing data between servers, and where it’s not a big deal if you occasionally lose that data for whatever reason

参考文章如下：

https://www.cnblogs.com/itrena/p/5926878.html
https://www.fuwuqizhijia.com/redis/201704/60935.html
https://blog.csdn.net/forezp/article/details/85081162
https://blog.csdn.net/xixingzhe2/article/details/86167859
http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

---

最后，也欢迎各位读者入群来交流切磋技术，戳这里：咱们来一起抱团取暖，好吗？

---END---

热文推荐